package array;
import java.util.*;
public class Ex215 {
    class Solution {
        //意思理解错了
        public int findKthLargestx(int[] nums, int k) {
            Set<Integer> set = new TreeSet<>((o1, o2) -> o2 - o1);
            int count = 0;
            for (int i = 0; i < nums.length; i++) {
                boolean isSuc = set.add(nums[i]);
            }
            System.out.println(set);
            for (int s: set) {
                count++;
                if (count == k) {
                    return s;
                }
            }
            return -1;
        }


        //使用大顶堆解决
        public int findKthLargest1(int[] nums, int k) {
            Queue<Integer> queue = new PriorityQueue<>((o1, o2) -> o2 - o1);
            int count = 0;
            for (int i = 0; i < nums.length; i++) {
                queue.offer(nums[i]);
            }
            System.out.println(queue);
            while (!queue.isEmpty()) {
                int res = queue.poll();
                count++;
                if (count == k) {
                    return res;
                }
            }
            return -1;
        }

        //通过小顶堆解决
        public int findKthLargest2(int[] nums, int k) {
            Queue<Integer> queue = new PriorityQueue<>((o1, o2) -> o1 - o2);
            int count = 0;
            for (int i = 0; i < nums.length; i++) {
                queue.offer(nums[i]);
            }
            System.out.println(queue);
            for (int i = 0; i < nums.length - k; i++) {
                queue.poll();
            }
            return queue.peek();
        }

        //其实，根本用不了O(n)的空间，只需要保留k个元素即可
         public int findKthLargest3(int[] nums, int k) {
            int len = nums.length;
            //只取len + 1个空间
            Queue<Integer> queue = new PriorityQueue<>(len + 1, (o1, o2) -> o1 - o2);

            for (int i = 0; i < k; i++) {
                queue.offer(nums[i]);
            }
            System.out.println(queue);
            for (int i = k; i < len; i++) {
                queue.offer(nums[i]);
                queue.poll(); //将不合理的小元素直接干掉，不占用额外空间
            }

            return queue.peek();
        }

        //同理，对于大顶堆也可以进行优化
         //其实，根本用不了O(n)的空间，只需要保留k个元素即可
         public int findKthLargest4(int[] nums, int k) {
            int len = nums.length;
            //只取len + 1个空间
            Queue<Integer> queue = new PriorityQueue<>(len, (o1, o2) -> o2 - o1);

            for (int i = 0; i < k; i++) {
                queue.offer(nums[i]); //先进入k个元素
            }

            for (int i = k; i < len; i++) {
                //若新元素比队头元素大，直接干掉队头小元素，适者生存
                if (nums[i] > queue.peek()) {
                    queue.poll();
                    queue.offer(nums[i]);
                }
            }

            return queue.peek();
        }

        //partion 剪治法
        //partion会使得每次进行划分使得一个元素回到他****最终所在的位置上***，因此可以判断这个位置是否满足要求或者干掉不满足要求的一半区间
        public int findKthLargest (int[] nums, int k) {
            int len = nums.length, lo = 0, hi = len - 1;
            while (true) {
                int p = partion(nums, lo, hi);
                if (p == len - k) return nums[p];
                else if (p < len - k) {
                    //当前第k大元素在右半边
                    lo = p + 1;
                } else {
                    // 第k大元素在p的左半边
                    hi = p - 1;
                }
            }
        }

        public int partion(int[] nums, int lo, int hi) {
            //为了减少极端情况【全正序或者全倒序导致快排退化到O(n^2)的时间复杂度】
            if (lo < hi) { //将lo的元素与lo + 1，lo + 2, ... hi其中任意一个元素互换
                Random random = new Random();
                int s = random.nextInt(hi - lo) + 1 + lo;
                swap(nums, lo, s);
            }

            int pivot = nums[lo], i = lo, j = hi;
            while (i < j) {
                while (i < j && nums[j] >= pivot) j--;
                while (i < j && nums[i] <= pivot) i++;
                swap(nums, i, j);
            }
            swap(nums, lo, i);
            return i;
        }

        public void swap(int[] nums, int i, int j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }
}
